import java.util.Stack;

public class TestSort1 {

    //插入排序

    /**
     * 时间复杂度:O(n^2)
     * 空间复杂度:O(1)
     * 稳定性:稳定(一个稳定的排序可以实现为一个不稳定的排序;但是不稳定的排序实现不了稳定的排序)
     * @param arr
     */
    public static void insertSort(int[] arr) {
        for(int i=1;i<arr.length;i++) {
            int tmp=arr[i];//tmp中存储是要插入的对象
            int j=i-1;
            for(;j>=0;j--) {   //将tmp前面的数一个个与tmp做比较
                if(arr[j]>tmp) {    //若是tmp更小,那么将该值后移
                    arr[j+1]=arr[j];
                }else {             //后移直到tmp更大时,跳出循环
                    break;
                }
            }
            arr[j+1]=tmp;
        }
    }

    /**
     * 不稳定
     *
     * @param arr
     */
    public static void shellSort(int[] arr) {
        int gap=arr.length;
        while(gap>1) {
            gap/=2;
            shell(arr,gap);
        }
    }
    /*
    每组进行插入排序
     */
    private static void shell(int[] arr,int gap) {
        for(int i=gap;i<arr.length;i++) {   //i++,交替进行插入排序
            int tmp=arr[i];
            int j=i-gap;
            for(;j>=0;j-=gap) {
                if(arr[j]>tmp) {
                    arr[j+gap]=arr[j];
                }else {
                    break;
                }
            }
            arr[j+gap]=tmp;
        }
    }

    /**
     * 选择排序
     * 时间复杂度:O(n^2)
     * 空间复杂度:O(1)
     * 稳定性:稳定(一个稳定的排序可以实现为一个不稳定的排序;但是不稳定的排序实现不了稳定的排序)
     * @param arr
     */
    public static void selectSort1(int[] arr) {
        for(int i=0;i<arr.length;i++) {
            //每次将当前的i下标当做最小值与后面的进行比较
            int minIndex=i;
            for(int j=i+1;j<arr.length;j++) {   //j去遍历i后面的所有元素
                if(arr[j]<arr[minIndex]) {  //找到了更小的,赋值给minIndex
                    minIndex=j;
                }
            }
            //走完for循环后,minIndex存储的就是最小值的下标
            swap(arr,i,minIndex);//将i下标的值换成找到的最小值
        }
    }
    private static void swap(int[] array,int i,int j) {
        int tmp=array[i];
        array[i]=array[j];
        array[j]=tmp;
    }

    /**
     * 时间复杂度:O(n^2)
     * @param arr
     */
    public static void selectSort2(int[] arr) {
        int left=0;
        int right=arr.length-1;
        while(left<right) {
            int minIndex=left;
            int maxIndex=left;
            for(int i=left+1;i<=right;i++) {
                if(arr[i]<arr[minIndex]) {
                    minIndex=i;
                }
                if(arr[i]>arr[maxIndex]) {
                    maxIndex=i;
                }
            }
            //minIndex存了最小值下标,maxIndex存了最大值下标
            swap(arr,minIndex,left);
            if(maxIndex==left){
                maxIndex=minIndex;
            }
            swap(arr,maxIndex,right);
            left++;
            right--;
        }
    }


    public static void heapSort(int[] arr) {
        createBigHeap(arr);//先创建一个大根堆
        int end=arr.length-1;
        while(end>=0) {
            swap(arr,0,end);
            siftDown(0,arr,end);
            end--;
        }
    }
    private static void createBigHeap(int[] arr) {
        for(int parent=(arr.length-1-1)/2;parent>=0;parent--) {
            siftDown(parent,arr,arr.length);
        }
    }
    private static void siftDown(int parent,int[] arr,int end) {
        int child=2*parent+1;
        while(child<end) {
            if(child+1<end && arr[child]<arr[child+1]) {
                child++;
            }
            //child下标是左右孩子最大值的下标
            if(arr[child]>arr[parent]) {
                swap(arr,child,parent);
                parent=child;
                child=2*parent+1;
            }else {
                break;
            }
        }
    }

    /**
     * 优化前:O(n^2),优化后当数据有序时,时间复杂度为O(n)
     * O(1)
     * 稳定(插入,冒泡)
     * 不稳定(希尔,选择,堆)
     * @param arr
     */
    public static void bubbleSort(int[] arr) {
        for(int i=0;i<arr.length;i++) {
            boolean flag=true;
            for(int j=0;j<arr.length-i-1;j++) {
                if(arr[j]>arr[j+1]) {
                    swap(arr,j,j+1);
                    flag=false;
                }
            }
            if(flag) {
                break;//若是走了一趟flag仍为true,说明这一趟没有进行任何操作,说明已经有序了
            }
        }
    }


    public static void quickSort(int[] arr) {
        quick(arr,0,arr.length-1);
    }
    private static void quick(int[] array,int start,int end) {
        if(start>=end) {
            return;   //当新一轮调整开始时发现,start与end相等或者start在end右边,那么说明这一轮只有一个元素,已经是有序的了,那么就返回
        }

        //在小区间用插入排序,减少递归次数
        if(end-start+1<=10) {
            insertSortRange(array,start,end);
            return;
        }

        //System.out.println("start:"+start+" end:"+end);

        //进行三数取中,找到left,right和m中的中位数,将其与left进行交换,作为基准值
        //1 2 3 4 5 -> 3 2 1 4 5
        int index=midThreeNum(array,start,end);
        swap(array,start,index);

        int pivot=partition(array,start,end);
        quick(array,start,pivot-1);//递归par的左边
        quick(array,pivot+1,end);//递归par的右边
    }
    //找到left和right相遇的地方
    private static int partitionHoare(int[] array,int left,int right) {
        int i=left;//标记基准值的位置
        int tmp=array[left];
        while(left<right) {
            //right往前找小于tmp的,left往后找大于tmp的,找到了交换
            while(left<right && array[right]>=tmp) {    //要加上left<right,比如若数据是完全有序的,那么所有元素逗比tmp小,left一直走,就会越界
                right--;
            }
            while(left<right && array[left]<=tmp) {
                left++;
            }
            //找到了
            swap(array,left,right);
        }
        //相遇了,让相遇位置和基准位置交换
        swap(array,i,left);
        return left;//返回新基准位置
    }

    private static int partition(int[] array,int left,int right) {
        int tmp=array[left];
        while(left<right) {
            while(left<right && array[right]>=tmp) {
              right--;
            }
            array[left]=array[right];
            while(left<right && array[left]<=tmp) {
                left++;
            }
            array[right]=array[left];
        }
        array[left]=tmp;
        return left;
    }

    //找到left,right,mid中的中位数并返回它的下标
    private static int midThreeNum(int[] array,int left,int right) {
        int mid=(left+right)/2;
        if (array[left] < array[right]) {
            if(array[mid]<array[left]) {
                return left;
            }else if(array[mid]>array[right]) {
                return right;
            }else {
                return mid;
            }
        }else {
            if(array[mid]<array[right]) {
                return right;
            }else if(array[mid]>array[left]) {
                return left;
            }else {
                return mid;
            }
        }
    }

    public static void insertSortRange(int[] arr,int left,int right) {
        for(int i=left+1;i<=right;i++) {
            int tmp=arr[i];//tmp中存储是要插入的对象
            int j=i-1;
            for(;j>=left;j--) {   //将tmp前面的数一个个与tmp做比较
                if(arr[j]>tmp) {    //若是tmp更小,那么将该值后移
                    arr[j+1]=arr[j];
                }else {             //后移直到tmp更大时,跳出循环
                    break;
                }
            }
            arr[j+1]=tmp;
        }
    }

    public static void quickSortNot(int[] arr) {
        Stack<Integer> stack=new Stack<>();
        int left=0;
        int right=arr.length-1;
        int par=partition(arr,left,right);

        if(par>left+1) {
            //入栈
            stack.push(left);
            stack.push(par-1);
        }
        if(par<right-1) {
            stack.push(par+1);
            stack.push(right);
        }
        while(!stack.isEmpty()) {
            right=stack.pop();
            left=stack.pop();
            par=partition(arr,left,right);//找到新的分组元素
            if(par>left+1) {
                //入栈
                stack.push(left);
                stack.push(par-1);
            }
            if(par<right-1) {
                stack.push(par+1);
                stack.push(right);
            }
        }
    }

    public static void mergeSort(int[] arr) {
        mergeSortFunc(arr,0,arr.length-1);
    }
    public static void mergeSortFunc(int[] arr,int left,int right) {
        if(left>=right) return;//分解成只有一个元素了,返回
        int mid=(left+right)/2;
        mergeSortFunc(arr,left,mid);
        mergeSortFunc(arr,mid+1,right);
        //合并
        merge(arr,left,mid,right);
    }
    private static void merge(int[] arr,int left,int mid,int right) {
        int[] tmp=new int[right-left+1];
        int k=0;
        int s1=left;
        int e1=mid;
        int s2=mid+1;
        int e2=right;
        while(s1<=e1 && s2<=e2) {
            if(arr[s1]<=arr[s2]) {
                tmp[k++] = arr[s1++];
            } else {
                tmp[k++] = arr[s2++];
            }
        }
        while(s1<=e1) {
            tmp[k++] = arr[s1++];
        }
        while(s2<=e2) {
            tmp[k++] = arr[s2++];
        }
        //将tmp数组拷贝回array数组中
        for(int i=0;i<k;i++) {
            arr[i+left]=tmp[i];
        }
    }

    /**
     * 非递归的归并排序
     */
    public static void mergeSortNot(int[] arr) {
        int gap=1;
        while(gap<arr.length) {
            for(int i=0;i<arr.length;i+=2*gap) {
                int left=i;
                int mid=left+gap-1;
                if(mid>=arr.length) {
                    mid=arr.length-1;//防止mid越界
                }
                int right=mid+gap;
                if(right>=arr.length) {
                    right=arr.length-1;//防止mid越界
                }
                merge(arr,left,mid,right);
            }
            gap*=2;
        }
    }

    //计数排序
    public static void countSort(int[] arr) {
        int maxVal=arr[0];
        int minVal=arr[0];
        for(int i=0;i<arr.length;i++) {
            if(maxVal<arr[i]) {
                maxVal=arr[i];
            }
            if(minVal>arr[i]) {
                minVal=arr[i];
            }
        }
        int len=maxVal-minVal+1;
        int[] count=new int[len];
        for(int i=0;i<arr.length;i++) {
            count[arr[i]-minVal]++;
        }
        //计数数组构建完成,将它copy给原数组
        int index=0;//这是原数组的下标
        for(int i=0;i<len;i++) {
            int k=count[i];
            while(k>0) {
                arr[index++]=i+minVal;//放数据的时候减掉了minVal,copy的时候要加回来
                k--;
            }
        }
    }

}
